package com.zhangxiaofanfan.hotcode.second;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * TODO
 *
 * @date 2024-08-15 10:31:09
 * @author zhangxiaofanfan
 */
public class HotCode011 {
    public static void main(String[] args) {
        int[] nums = {1,3,-1,-3,5,3,6,7};
        int k = 3;
        HotCode011 hotCode = new HotCode011();
        System.out.println(Arrays.toString(hotCode.maxSlidingWindow(nums, k)));
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] result = new int[nums.length - k + 1];
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((num1, num2) -> Integer.compare(num2, num1));
        Map<Integer, Integer> map = new HashMap<>();
        int index = 0;
        for (index = 0; index < k; index++) {
            priorityQueue.add(nums[index]);
        }
        for (int i = 0; i < result.length; i++) {
            while (map.getOrDefault(priorityQueue.peek(), 0) > 0) {
                Integer remove = priorityQueue.remove();
                map.put(remove, map.get(remove) - 1);
                if (map.get(remove) <= 0) {
                    map.remove(remove);
                }
            }
            result[i] = priorityQueue.peek();
            if (i != result.length - 1) {
                map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
                priorityQueue.add(nums[i + k]);
            }
        }
        return result;
    }
}
